<html>
 <head>
  <meta charset="utf-8"/>
  <meta content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no" name="viewport"/>
  <title>
   中文分词算法 之 基于词典的正向最大匹配算法  | 数螺 | NAUT IDEA
  </title>
  <link href="http://cdn.bootcss.com/bootstrap/3.3.6/css/bootstrap-theme.min.css" rel="stylesheet"/>
  <link href="http://cdn.bootcss.com/bootstrap/3.3.6/css/bootstrap.min.css" rel="stylesheet"/>
  <style type="text/css">
   #xmain img {
                  max-width: 100%;
                  display: block;
                  margin-top: 10px;
                  margin-bottom: 10px;
                }

                #xmain p {
                    line-height:150%;
                    font-size: 16px;
                    margin-top: 20px;
                }

                #xmain h2 {
                    font-size: 24px;
                }

                #xmain h3 {
                    font-size: 20px;
                }

                #xmain h4 {
                    font-size: 18px;
                }


                .header {
	           background-color: #0099ff;
	           color: #ffffff;
	           margin-bottom: 20px;
	        }

	        .header p {
                  margin: 0px;
                  padding: 10px 0;
                  display: inline-block;  
                  vertical-align: middle;
                  font-size: 16px;
               }

               .header a {
                 color: white;
               }

              .header img {
                 height: 25px;
              }
  </style>
  <script src="http://cdn.bootcss.com/jquery/3.0.0/jquery.min.js">
  </script>
  <script src="http://nautstatic-10007657.file.myqcloud.com/static/css/readability.min.js" type="text/javascript">
  </script>
  <script type="text/javascript">
   $(document).ready(function() {
                 var loc = document.location;
                 var uri = {
                  spec: "http://dataunion.org/16370.html",
                  host: "http://dataunion.org",
                  prePath: "http://dataunion.org",
                  scheme: "http",
                  pathBase: "http://dataunion.org/"
                 };
    
                 var documentClone = document.cloneNode(true);
                 var article = new Readability(uri, documentClone).parse();
     
                 document.getElementById("xmain").innerHTML = article.content;
                });
  </script>
  <!-- 1466461327: Accept with keywords: (title(0.166666666667):中文,词典,社区,数盟,算法,分词, topn(0.3):初始化,社区,数目,节省,数盟,空白,查找,内存,数组,长度,序列表,重构,遍历,前缀,分词,未找到,文章,数量级,方法,节点,中文,性能,算法,有序,优化,词典,字符,数据,代码,次测试).-->
 </head>
 <body onload="">
  <div class="header">
   <div class="container">
    <div class="row">
     <div class="col-xs-6 col-sm-6 text-left">
      <a href="/databee">
       <img src="http://nautidea-10007657.cos.myqcloud.com/logo_white.png"/>
      </a>
      <a href="/databee">
       <p>
        数螺
       </p>
      </a>
     </div>
     <div class="hidden-xs col-sm-6 text-right">
      <p>
       致力于数据科学的推广和知识传播
      </p>
     </div>
    </div>
   </div>
  </div>
  <div class="container text-center">
   <h1>
    中文分词算法 之 基于词典的正向最大匹配算法
   </h1>
  </div>
  <div class="container" id="xmain">
   ﻿﻿
   <title>
    中文分词算法 之 基于词典的正向最大匹配算法 | 数盟社区
   </title>
   <!-- All in One SEO Pack 2.2.7.6.2 by Michael Torbert of Semper Fi Web Design[32,69] -->
   <!-- /all in one seo pack -->
   <!--
<div align="center">
<a href="http://strata.oreilly.com.cn/hadoop-big-data-cn?cmp=mp-data-confreg-home-stcn16_dataunion_pc" target="_blank"><img src="http://dataunion.org/wp-content/uploads/2016/05/stratabj.jpg"/ ></a>
</div>
-->
   <header id="header-web">
    <div class="header-main">
     <hgroup class="logo">
      <h1>
       <a href="http://dataunion.org/" rel="home" title="数盟社区">
        <img src="http://dataunion.org/wp-content/themes/yzipi/images/logo.png"/>
       </a>
      </h1>
     </hgroup>
     <!--logo-->
     <nav class="header-nav">
      <ul class="menu" id="menu-%e4%b8%bb%e8%8f%9c%e5%8d%95">
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-71" id="menu-item-71">
        <a href="http://dataunion.org/category/events" title="events">
         活动
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-22457" id="menu-item-22457">
          <a href="http://dataunion.org/2016timeline">
           2016档期
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-22459" id="menu-item-22459">
          <a href="http://dataunion.org/category/parterc">
           合作会议
          </a>
         </li>
        </ul>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category current-post-ancestor current-menu-parent current-post-parent menu-item-has-children menu-item-20869" id="menu-item-20869">
        <a href="http://dataunion.org/category/tech" title="articles">
         文章
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-20867" id="menu-item-20867">
          <a href="http://dataunion.org/category/tech/base" title="base">
           基础架构
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3302" id="menu-item-3302">
          <a href="http://dataunion.org/category/tech/ai" title="ai">
           人工智能
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3303" id="menu-item-3303">
          <a href="http://dataunion.org/category/tech/analysis" title="analysis">
           数据分析
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-21920" id="menu-item-21920">
          <a href="http://dataunion.org/category/tech/dm">
           数据挖掘
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3314" id="menu-item-3314">
          <a href="http://dataunion.org/category/tech/viz" title="viz">
           可视化
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3305" id="menu-item-3305">
          <a href="http://dataunion.org/category/tech/devl" title="devl">
           编程语言
          </a>
         </li>
        </ul>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-20876" id="menu-item-20876">
        <a href="http://dataunion.org/category/industry">
         行业
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-16328" id="menu-item-16328">
          <a href="http://dataunion.org/category/industry/case" title="case">
           行业应用
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-2112" id="menu-item-2112">
          <a href="http://dataunion.org/category/industry/demo" title="demo">
           Demo展示
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-21562" id="menu-item-21562">
          <a href="http://dataunion.org/category/industry/news">
           行业资讯
          </a>
         </li>
        </ul>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-311" id="menu-item-311">
        <a href="http://dataunion.org/category/sources" title="sources">
         资源
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-20870" id="menu-item-20870">
        <a href="http://dataunion.org/category/books" title="book">
         图书
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-21363" id="menu-item-21363">
        <a href="http://dataunion.org/category/training">
         课程
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-21853" id="menu-item-21853">
        <a href="http://dataunion.org/category/jobs">
         职位
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-22050" id="menu-item-22050">
          <a href="http://dataunion.org/category/career">
           职业规划
          </a>
         </li>
        </ul>
       </li>
      </ul>
     </nav>
     <!--header-nav-->
    </div>
   </header>
   <!--header-web-->
   <div id="main">
    <div id="soutab">
     <form action="http://dataunion.org/" class="search" method="get">
     </form>
    </div>
    <div id="container">
     <nav id="mbx">
      当前位置：
      <a href="http://dataunion.org">
       首页
      </a>
      &gt;
      <a href="http://dataunion.org/category/tech">
       文章
      </a>
      &gt;  正文
     </nav>
     <!--mbx-->
     <article class="content">
      <header align="centre" class="contenttitle">
       <div class="mscc">
        <h1 class="mscctitle">
         <a href="http://dataunion.org/16370.html">
          中文分词算法 之 基于词典的正向最大匹配算法
         </a>
        </h1>
        <address class="msccaddress ">
         <em>
          1,339 次阅读 -
         </em>
         <a href="http://dataunion.org/category/tech" rel="category tag">
          文章
         </a>
        </address>
       </div>
      </header>
      <div class="content-text">
       <p>
        基于词典的正向最大匹配算法（
        <strong>
         最长词优先匹配
        </strong>
        ），算法会根据词典文件自动调整最大长度，分词的好坏完全取决于词典。
       </p>
       <p>
       </p>
       <p>
        算法流程图如下：
       </p>
       <p>
        <img src="http://dataunion.org/wp-content/uploads/2015/05/ce25481b-ad85-3ed5-8891-ed002e42104e.png"/>
       </p>
       <p>
       </p>
       <p>
        Java实现代码如下：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          <span class="comment">
           /**
          </span>
         </li>
         <li>
          <span class="comment">
           * 基于词典的正向最大匹配算法
          </span>
         </li>
         <li>
          <span class="comment">
           * @author 杨尚川
          </span>
         </li>
         <li>
          <span class="comment">
           */
          </span>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           class
          </span>
          WordSeg {
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           static
          </span>
          <span class="keyword">
           final
          </span>
          List&lt;String&gt; DIC =
          <span class="keyword">
           new
          </span>
          ArrayList&lt;&gt;();
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           static
          </span>
          <span class="keyword">
           final
          </span>
          <span class="keyword">
           int
          </span>
          MAX_LENGTH;
         </li>
         <li>
          <span class="keyword">
           static
          </span>
          {
         </li>
         <li>
          <span class="keyword">
           try
          </span>
          {
         </li>
         <li>
          System.out.println(
          <span class="string">
           “开始初始化词典”
          </span>
          );
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          max=
          <span class="number">
           1
          </span>
          ;
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          count=
          <span class="number">
           0
          </span>
          ;
         </li>
         <li>
          List&lt;String&gt; lines = Files.readAllLines(Paths.get(
          <span class="string">
           “D:/dic.txt”
          </span>
          ), Charset.forName(
          <span class="string">
           “utf-8”
          </span>
          ));
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (String line : lines){
         </li>
         <li>
          DIC.add(line);
         </li>
         <li>
          count++;
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (line.length()&gt;max){
         </li>
         <li>
          max=line.length();
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
         <li>
          MAX_LENGTH = max;
         </li>
         <li>
          System.out.println(
          <span class="string">
           “完成初始化词典，词数目：”
          </span>
          +count);
         </li>
         <li>
          System.out.println(
          <span class="string">
           “最大分词长度：”
          </span>
          +MAX_LENGTH);
         </li>
         <li>
          }
          <span class="keyword">
           catch
          </span>
          (IOException ex) {
         </li>
         <li>
          System.err.println(
          <span class="string">
           “词典装载失败:”
          </span>
          +ex.getMessage());
         </li>
         <li>
          }
         </li>
         <li>
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           static
          </span>
          <span class="keyword">
           void
          </span>
          main(String[] args){
         </li>
         <li>
          String text =
          <span class="string">
           “杨尚川是APDPlat应用级产品开发平台的作者”
          </span>
          ;
         </li>
         <li>
          System.out.println(seg(text));
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           static
          </span>
          List&lt;String&gt; seg(String text){
         </li>
         <li>
          List&lt;String&gt; result =
          <span class="keyword">
           new
          </span>
          ArrayList&lt;&gt;();
         </li>
         <li>
          <span class="keyword">
           while
          </span>
          (text.length()&gt;
          <span class="number">
           0
          </span>
          ){
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          len=MAX_LENGTH;
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (text.length()&lt;len){
         </li>
         <li>
          len=text.length();
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //取指定的最大长度的文本去词典里面匹配
          </span>
         </li>
         <li>
          String tryWord = text.substring(
          <span class="number">
           0
          </span>
          ,
          <span class="number">
           0
          </span>
          +len);
         </li>
         <li>
          <span class="keyword">
           while
          </span>
          (!DIC.contains(tryWord)){
         </li>
         <li>
          <span class="comment">
           //如果长度为一且在词典中未找到匹配，则按长度为一切分
          </span>
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (tryWord.length()==
          <span class="number">
           1
          </span>
          ){
         </li>
         <li>
          <span class="keyword">
           break
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //如果匹配不到，则长度减一继续匹配
          </span>
         </li>
         <li>
          tryWord=tryWord.substring(
          <span class="number">
           0
          </span>
          , tryWord.length()-
          <span class="number">
           1
          </span>
          );
         </li>
         <li>
          }
         </li>
         <li>
          result.add(tryWord);
         </li>
         <li>
          <span class="comment">
           //从待分词文本中去除已经分词的文本
          </span>
         </li>
         <li>
          text=text.substring(tryWord.length());
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          result;
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
        词典文件下载地址
        <a href="http://pan.baidu.com/s/1i37gKLZ" target="_blank" title="http://pan.baidu.com/s/1i37gKLZ">
         dic.rar
        </a>
        ，简单吧，呵呵
       </p>
       <p>
       </p>
       <p>
        实现功能是简单，不过这里的词典中词的数目为：427452，我们需要频繁执行DIC.contains(tryWord))来判断一个词是否在词典中，所以优化这行代码能够显著提升分词效率（不要过早优化、不要做不成熟的优化）。
       </p>
       <p>
       </p>
       <p>
        上面的代码是利用了JDK的Collection接口的contains方法来判断一个词是否在词典中，而这个方法的不同实现，其性能差异极大，上面的初始版本是用了ArrayList：List&lt;String&gt; DIC = new ArrayList&lt;&gt;()。那么这个ArrayList的性能如何呢？还有更好性能的实现吗？
       </p>
       <p>
       </p>
       <p>
        通常来说，对于查找算法，在有序列表中查找比在无序列表中查找更快，分区查找比全局遍历要快。
       </p>
       <p>
       </p>
       <p>
        通过查看ArrayList、LinkedList、HashSet的contains方法的源代码，发现ArrayList和LinkedList采用全局遍历的方式且未利用有序列表的优势，HashSet使用了分区查找，如果hash分布均匀冲突少，则需要遍历的列表就很少甚至不需要。理论归理论，还是写个代码来测测更直观放心，测试代码如下：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          <span class="comment">
           /**
          </span>
         </li>
         <li>
          <span class="comment">
           * 比较词典查询算法的性能
          </span>
         </li>
         <li>
          <span class="comment">
           * @author 杨尚川
          </span>
         </li>
         <li>
          <span class="comment">
           */
          </span>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           class
          </span>
          SearchTest {
         </li>
         <li>
          <span class="comment">
           //为了生成随机查询的词列表
          </span>
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           static
          </span>
          <span class="keyword">
           final
          </span>
          List&lt;String&gt; DIC_FOR_TEST =
          <span class="keyword">
           new
          </span>
          ArrayList&lt;&gt;();
         </li>
         <li>
          <span class="comment">
           //通过更改这里DIC的实现来比较不同实现之间的性能
          </span>
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           static
          </span>
          <span class="keyword">
           final
          </span>
          List&lt;String&gt; DIC =
          <span class="keyword">
           new
          </span>
          ArrayList&lt;&gt;();
         </li>
         <li>
          <span class="keyword">
           static
          </span>
          {
         </li>
         <li>
          <span class="keyword">
           try
          </span>
          {
         </li>
         <li>
          System.out.println(
          <span class="string">
           “开始初始化词典”
          </span>
          );
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          count=
          <span class="number">
           0
          </span>
          ;
         </li>
         <li>
          List&lt;String&gt; lines = Files.readAllLines(Paths.get(
          <span class="string">
           “D:/dic.txt”
          </span>
          ), Charset.forName(
          <span class="string">
           “utf-8”
          </span>
          ));
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (String line : lines){
         </li>
         <li>
          DIC.add(line);
         </li>
         <li>
          DIC_FOR_TEST.add(line);
         </li>
         <li>
          count++;
         </li>
         <li>
          }
         </li>
         <li>
          System.out.println(
          <span class="string">
           “完成初始化词典，词数目：”
          </span>
          +count);
         </li>
         <li>
          }
          <span class="keyword">
           catch
          </span>
          (IOException ex) {
         </li>
         <li>
          System.err.println(
          <span class="string">
           “词典装载失败:”
          </span>
          +ex.getMessage());
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           static
          </span>
          <span class="keyword">
           void
          </span>
          main(String[] args){
         </li>
         <li>
          <span class="comment">
           //选取随机值
          </span>
         </li>
         <li>
          List&lt;String&gt; words =
          <span class="keyword">
           new
          </span>
          ArrayList&lt;&gt;();
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (
          <span class="keyword">
           int
          </span>
          i=
          <span class="number">
           0
          </span>
          ;i&lt;
          <span class="number">
           100000
          </span>
          ;i++){
         </li>
         <li>
          words.add(DIC_FOR_TEST.get(
          <span class="keyword">
           new
          </span>
          Random(System.nanoTime()+i).nextInt(
          <span class="number">
           427452
          </span>
          )));
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           long
          </span>
          start = System.currentTimeMillis();
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (String word : words){
         </li>
         <li>
          DIC.contains(word);
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           long
          </span>
          cost = System.currentTimeMillis()-start;
         </li>
         <li>
          System.out.println(
          <span class="string">
           “cost time:”
          </span>
          +cost+
          <span class="string">
           ” ms”
          </span>
          );
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
        </ol>
       </div>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          #分别运行
          <span class="number">
           10
          </span>
          次测试，然后取平均值
         </li>
         <li>
          LinkedList
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           48812
          </span>
          ms
         </li>
         <li>
          ArrayList
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           40219
          </span>
          ms
         </li>
         <li>
          HashSet
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           8
          </span>
          ms
         </li>
         <li>
          HashSet
          <span class="number">
           1000000
          </span>
          次查询     cost time:
          <span class="number">
           258
          </span>
          ms
         </li>
         <li>
          HashSet
          <span class="number">
           100000000
          </span>
          次查询   cost time:
          <span class="number">
           28575
          </span>
          ms
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
        我们发现HashSet性能最好，比LinkedList和ArrayList快约3个数量级！这个测试结果跟前面的分析一致，LinkedList要比ArrayList慢一些，虽然他们都是全局遍历，但是LinkedList需要操作下一个数据的引用，所以会多一些操作，LinkedList因为需要保存前驱和后继引用，占用的内存也要高一些。
       </p>
       <p>
       </p>
       <p>
        虽然HashSet已经有不错的性能了，但是如果词典越来越大，内存占用越来越多怎么办？如果有一个数据结构，有接近HashSet性能的同时，又能对词典的数据进行压缩以减少内存占用，那就完美了。
       </p>
       <p>
       </p>
       <p>
        前缀树（Trie）有可能可以实现“鱼与熊掌兼得”的好事，自己实现一个Trie的数据结构，代码如下：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          <span class="comment">
           /**
          </span>
         </li>
         <li>
          <span class="comment">
           * 前缀树的Java实现
          </span>
         </li>
         <li>
          <span class="comment">
           * 用于查找一个指定的字符串是否在词典中
          </span>
         </li>
         <li>
          <span class="comment">
           * @author 杨尚川
          </span>
         </li>
         <li>
          <span class="comment">
           */
          </span>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           class
          </span>
          Trie {
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           final
          </span>
          TrieNode ROOT_NODE =
          <span class="keyword">
           new
          </span>
          TrieNode(
          <span class="string">
           ‘/’
          </span>
          );
         </li>
         <li>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           boolean
          </span>
          contains(String item){
         </li>
         <li>
          <span class="comment">
           //去掉首尾空白字符
          </span>
         </li>
         <li>
          item=item.trim();
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          len = item.length();
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (len &lt;
          <span class="number">
           1
          </span>
          ){
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          <span class="keyword">
           false
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //从根节点开始查找
          </span>
         </li>
         <li>
          TrieNode node = ROOT_NODE;
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (
          <span class="keyword">
           int
          </span>
          i=
          <span class="number">
           0
          </span>
          ;i&lt;len;i++){
         </li>
         <li>
          <span class="keyword">
           char
          </span>
          character = item.charAt(i);
         </li>
         <li>
          TrieNode child = node.getChild(character);
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (child ==
          <span class="keyword">
           null
          </span>
          ){
         </li>
         <li>
          <span class="comment">
           //未找到匹配节点
          </span>
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          <span class="keyword">
           false
          </span>
          ;
         </li>
         <li>
          }
          <span class="keyword">
           else
          </span>
          {
         </li>
         <li>
          <span class="comment">
           //找到节点，继续往下找
          </span>
         </li>
         <li>
          node = child;
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (node.isTerminal()){
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          <span class="keyword">
           true
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          <span class="keyword">
           false
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          addAll(List&lt;String&gt; items){
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (String item : items){
         </li>
         <li>
          add(item);
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          add(String item){
         </li>
         <li>
          <span class="comment">
           //去掉首尾空白字符
          </span>
         </li>
         <li>
          item=item.trim();
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          len = item.length();
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (len &lt;
          <span class="number">
           1
          </span>
          ){
         </li>
         <li>
          <span class="comment">
           //长度小于1则忽略
          </span>
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //从根节点开始添加
          </span>
         </li>
         <li>
          TrieNode node = ROOT_NODE;
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (
          <span class="keyword">
           int
          </span>
          i=
          <span class="number">
           0
          </span>
          ;i&lt;len;i++){
         </li>
         <li>
          <span class="keyword">
           char
          </span>
          character = item.charAt(i);
         </li>
         <li>
          TrieNode child = node.getChildIfNotExistThenCreate(character);
         </li>
         <li>
          <span class="comment">
           //改变顶级节点
          </span>
         </li>
         <li>
          node = child;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //设置终结字符，表示从根节点遍历到此是一个合法的词
          </span>
         </li>
         <li>
          node.setTerminal(
          <span class="keyword">
           true
          </span>
          );
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           static
          </span>
          <span class="keyword">
           class
          </span>
          TrieNode{
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           char
          </span>
          character;
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           boolean
          </span>
          terminal;
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           final
          </span>
          Map&lt;Character,TrieNode&gt; children =
          <span class="keyword">
           new
          </span>
          ConcurrentHashMap&lt;&gt;();
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          TrieNode(
          <span class="keyword">
           char
          </span>
          character){
         </li>
         <li>
          <span class="keyword">
           this
          </span>
          .character = character;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           boolean
          </span>
          isTerminal() {
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          terminal;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          setTerminal(
          <span class="keyword">
           boolean
          </span>
          terminal) {
         </li>
         <li>
          <span class="keyword">
           this
          </span>
          .terminal = terminal;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           char
          </span>
          getCharacter() {
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          character;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          setCharacter(
          <span class="keyword">
           char
          </span>
          character) {
         </li>
         <li>
          <span class="keyword">
           this
          </span>
          .character = character;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          Collection&lt;TrieNode&gt; getChildren() {
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          <span class="keyword">
           this
          </span>
          .children.values();
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          TrieNode getChild(
          <span class="keyword">
           char
          </span>
          character) {
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          <span class="keyword">
           this
          </span>
          .children.get(character);
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          TrieNode getChildIfNotExistThenCreate(
          <span class="keyword">
           char
          </span>
          character) {
         </li>
         <li>
          TrieNode child = getChild(character);
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (child ==
          <span class="keyword">
           null
          </span>
          ){
         </li>
         <li>
          child =
          <span class="keyword">
           new
          </span>
          TrieNode(character);
         </li>
         <li>
          addChild(child);
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          child;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          addChild(TrieNode child) {
         </li>
         <li>
          <span class="keyword">
           this
          </span>
          .children.put(child.getCharacter(), child);
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          removeChild(TrieNode child) {
         </li>
         <li>
          <span class="keyword">
           this
          </span>
          .children.remove(child.getCharacter());
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
         <li>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          show(){
         </li>
         <li>
          show(ROOT_NODE,
          <span class="string">
           “”
          </span>
          );
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           void
          </span>
          show(TrieNode node, String indent){
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (node.isTerminal()){
         </li>
         <li>
          System.out.println(indent+node.getCharacter()+
          <span class="string">
           “(T)”
          </span>
          );
         </li>
         <li>
          }
          <span class="keyword">
           else
          </span>
          {
         </li>
         <li>
          System.out.println(indent+node.getCharacter());
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (TrieNode item : node.getChildren()){
         </li>
         <li>
          show(item,indent+
          <span class="string">
           “\t”
          </span>
          );
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           static
          </span>
          <span class="keyword">
           void
          </span>
          main(String[] args){
         </li>
         <li>
          Trie trie =
          <span class="keyword">
           new
          </span>
          Trie();
         </li>
         <li>
          trie.add(
          <span class="string">
           “APDPlat”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “APP”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “APD”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “Nutch”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “Lucene”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “Hadoop”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “Solr”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “杨尚川”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “杨尚昆”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “杨尚喜”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “中华人民共和国”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “中华人民打太极”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “中华”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “中心思想”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “杨家将”
          </span>
          );
         </li>
         <li>
          trie.show();
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
       </p>
       <p>
        修改前面的测试代码，把List&lt;String&gt; DIC = new ArrayList&lt;&gt;()改为Trie DIC = new Trie()，使用Trie来做词典查找，最终的测试结果如下：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          #分别运行
          <span class="number">
           10
          </span>
          次测试，然后取平均值
         </li>
         <li>
          LinkedList
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           48812
          </span>
          ms
         </li>
         <li>
          ArrayList
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           40219
          </span>
          ms
         </li>
         <li>
          HashSet
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           8
          </span>
          ms
         </li>
         <li>
          HashSet
          <span class="number">
           1000000
          </span>
          次查询     cost time:
          <span class="number">
           258
          </span>
          ms
         </li>
         <li>
          HashSet
          <span class="number">
           100000000
          </span>
          次查询   cost time:
          <span class="number">
           28575
          </span>
          ms
         </li>
         <li>
          Trie
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           15
          </span>
          ms
         </li>
         <li>
          Trie
          <span class="number">
           1000000
          </span>
          次查询     cost time:
          <span class="number">
           1024
          </span>
          ms
         </li>
         <li>
          Trie
          <span class="number">
           100000000
          </span>
          次查询   cost time:
          <span class="number">
           104635
          </span>
          ms
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
        可以发现Trie和HashSet的性能差异较小，在半个数量级以内，通过jvisualvm惊奇地发现Trie占用的内存比HashSet的大约2.6倍，如下图所示：
       </p>
       <p>
       </p>
       <p>
        <strong>
         HashSet:
        </strong>
        <br/>
        <img src="http://dataunion.org/wp-content/uploads/2015/05/c08fc361-8b89-3be4-a14f-98c8ef054831.png"/>
        <br/>
        <strong>
         Trie:
        </strong>
       </p>
       <p>
        <img src="http://dataunion.org/wp-content/uploads/2015/05/4b1c723f-e4ff-3c4a-8a67-3ce2f40c633d.png"/>
       </p>
       <p>
       </p>
       <p>
        词典中词的数目为427452，HashSet是基于HashMap实现的，所以我们看到占内存最多的是HashMap$Node、char[]和String，手动执行GC多次，这三种类型的实例数一直在变化，当然都始终大于词数427452。Trie是基于ConcurrentHashMap实现的，所以我们看到占内存最多的是ConcurrentHashMap、ConcurrentHashMap$Node[]、ConcurrentHashMap$Node、Trie$TrieNode和Character，手动执行GC多次，发现Trie$TrieNode的实例数一直保持不变，说明427452个词经过Trie处理后的节点数为603141。
       </p>
       <p>
       </p>
       <p>
        很明显地可以看到，这里Trie的实现不够好，选用ConcurrentHashMap占用的内存相当大，那么我们如何来改进呢？把ConcurrentHashMap替换为HashMap可以吗？HashSet不是也基于HashMap吗？看看把ConcurrentHashMap替换为HashMap后的效果，如下图所示：
        <br/>
        <img src="http://dataunion.org/wp-content/uploads/2015/05/5018baaa-8eb8-3f57-9cc4-95fb2080dfa6.png"/>
        <br/>
        内存占用虽然少了10M左右，但仍然是HashSet的约2.4倍，本来是打算使用Trie来节省内存，没想反正更加占用内存了，既然使用HashMap来实现Trie占用内存极高，那么试试使用数组的方式，如下代码所示：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          <span class="comment">
           /**
          </span>
         </li>
         <li>
          <span class="comment">
           * 前缀树的Java实现
          </span>
         </li>
         <li>
          <span class="comment">
           * 用于查找一个指定的字符串是否在词典中
          </span>
         </li>
         <li>
          <span class="comment">
           * @author 杨尚川
          </span>
         </li>
         <li>
          <span class="comment">
           */
          </span>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           class
          </span>
          TrieV2 {
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           final
          </span>
          TrieNode ROOT_NODE =
          <span class="keyword">
           new
          </span>
          TrieNode(
          <span class="string">
           ‘/’
          </span>
          );
         </li>
         <li>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           boolean
          </span>
          contains(String item){
         </li>
         <li>
          <span class="comment">
           //去掉首尾空白字符
          </span>
         </li>
         <li>
          item=item.trim();
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          len = item.length();
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (len &lt;
          <span class="number">
           1
          </span>
          ){
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          <span class="keyword">
           false
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //从根节点开始查找
          </span>
         </li>
         <li>
          TrieNode node = ROOT_NODE;
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (
          <span class="keyword">
           int
          </span>
          i=
          <span class="number">
           0
          </span>
          ;i&lt;len;i++){
         </li>
         <li>
          <span class="keyword">
           char
          </span>
          character = item.charAt(i);
         </li>
         <li>
          TrieNode child = node.getChild(character);
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (child ==
          <span class="keyword">
           null
          </span>
          ){
         </li>
         <li>
          <span class="comment">
           //未找到匹配节点
          </span>
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          <span class="keyword">
           false
          </span>
          ;
         </li>
         <li>
          }
          <span class="keyword">
           else
          </span>
          {
         </li>
         <li>
          <span class="comment">
           //找到节点，继续往下找
          </span>
         </li>
         <li>
          node = child;
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (node.isTerminal()){
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          <span class="keyword">
           true
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          <span class="keyword">
           false
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          addAll(List&lt;String&gt; items){
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (String item : items){
         </li>
         <li>
          add(item);
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          add(String item){
         </li>
         <li>
          <span class="comment">
           //去掉首尾空白字符
          </span>
         </li>
         <li>
          item=item.trim();
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          len = item.length();
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (len &lt;
          <span class="number">
           1
          </span>
          ){
         </li>
         <li>
          <span class="comment">
           //长度小于1则忽略
          </span>
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //从根节点开始添加
          </span>
         </li>
         <li>
          TrieNode node = ROOT_NODE;
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (
          <span class="keyword">
           int
          </span>
          i=
          <span class="number">
           0
          </span>
          ;i&lt;len;i++){
         </li>
         <li>
          <span class="keyword">
           char
          </span>
          character = item.charAt(i);
         </li>
         <li>
          TrieNode child = node.getChildIfNotExistThenCreate(character);
         </li>
         <li>
          <span class="comment">
           //改变顶级节点
          </span>
         </li>
         <li>
          node = child;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //设置终结字符，表示从根节点遍历到此是一个合法的词
          </span>
         </li>
         <li>
          node.setTerminal(
          <span class="keyword">
           true
          </span>
          );
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           static
          </span>
          <span class="keyword">
           class
          </span>
          TrieNode{
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           char
          </span>
          character;
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           boolean
          </span>
          terminal;
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          TrieNode[] children =
          <span class="keyword">
           new
          </span>
          TrieNode[
          <span class="number">
           0
          </span>
          ];
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          TrieNode(
          <span class="keyword">
           char
          </span>
          character){
         </li>
         <li>
          <span class="keyword">
           this
          </span>
          .character = character;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           boolean
          </span>
          isTerminal() {
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          terminal;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          setTerminal(
          <span class="keyword">
           boolean
          </span>
          terminal) {
         </li>
         <li>
          <span class="keyword">
           this
          </span>
          .terminal = terminal;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           char
          </span>
          getCharacter() {
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          character;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          setCharacter(
          <span class="keyword">
           char
          </span>
          character) {
         </li>
         <li>
          <span class="keyword">
           this
          </span>
          .character = character;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          Collection&lt;TrieNode&gt; getChildren() {
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          Arrays.asList(children);
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          TrieNode getChild(
          <span class="keyword">
           char
          </span>
          character) {
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (TrieNode child : children){
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (child.getCharacter() == character){
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          child;
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          <span class="keyword">
           null
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          TrieNode getChildIfNotExistThenCreate(
          <span class="keyword">
           char
          </span>
          character) {
         </li>
         <li>
          TrieNode child = getChild(character);
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (child ==
          <span class="keyword">
           null
          </span>
          ){
         </li>
         <li>
          child =
          <span class="keyword">
           new
          </span>
          TrieNode(character);
         </li>
         <li>
          addChild(child);
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          child;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          addChild(TrieNode child) {
         </li>
         <li>
          children = Arrays.copyOf(children, children.length+
          <span class="number">
           1
          </span>
          );
         </li>
         <li>
          <span class="keyword">
           this
          </span>
          .children[children.length-
          <span class="number">
           1
          </span>
          ]=child;
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
         <li>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          show(){
         </li>
         <li>
          show(ROOT_NODE,
          <span class="string">
           “”
          </span>
          );
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           void
          </span>
          show(TrieNode node, String indent){
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (node.isTerminal()){
         </li>
         <li>
          System.out.println(indent+node.getCharacter()+
          <span class="string">
           “(T)”
          </span>
          );
         </li>
         <li>
          }
          <span class="keyword">
           else
          </span>
          {
         </li>
         <li>
          System.out.println(indent+node.getCharacter());
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (TrieNode item : node.getChildren()){
         </li>
         <li>
          show(item,indent+
          <span class="string">
           “\t”
          </span>
          );
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           static
          </span>
          <span class="keyword">
           void
          </span>
          main(String[] args){
         </li>
         <li>
          TrieV2 trie =
          <span class="keyword">
           new
          </span>
          TrieV2();
         </li>
         <li>
          trie.add(
          <span class="string">
           “APDPlat”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “APP”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “APD”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “杨尚川”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “杨尚昆”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “杨尚喜”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “中华人民共和国”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “中华人民打太极”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “中华”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “中心思想”
          </span>
          );
         </li>
         <li>
          trie.add(
          <span class="string">
           “杨家将”
          </span>
          );
         </li>
         <li>
          trie.show();
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
       </p>
       <p>
        内存占用情况如下图所示：
        <br/>
        <img src="http://dataunion.org/wp-content/uploads/2015/05/e5d91596-3fab-34cb-a9a6-cffd85223f4b.png"/>
        <br/>
        现在内存占用只有HashSet方式的80%了，内存问题总算是解决了，进一步分析，如果词典够大，词典中有共同前缀的词足够多，节省的内存空间一定非常客观。那么性能呢？看如下重新测试的数据：
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          #分别运行
          <span class="number">
           10
          </span>
          次测试，然后取平均值
         </li>
         <li>
          LinkedList
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           48812
          </span>
          ms
         </li>
         <li>
          ArrayList
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           40219
          </span>
          ms
         </li>
         <li>
          HashSet
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           8
          </span>
          ms
         </li>
         <li>
          HashSet
          <span class="number">
           1000000
          </span>
          次查询     cost time:
          <span class="number">
           258
          </span>
          ms
         </li>
         <li>
          HashSet
          <span class="number">
           100000000
          </span>
          次查询   cost time:
          <span class="number">
           28575
          </span>
          ms
         </li>
         <li>
          Trie
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           15
          </span>
          ms
         </li>
         <li>
          Trie
          <span class="number">
           1000000
          </span>
          次查询     cost time:
          <span class="number">
           1024
          </span>
          ms
         </li>
         <li>
          Trie
          <span class="number">
           100000000
          </span>
          次查询   cost time:
          <span class="number">
           104635
          </span>
         </li>
         <li>
          TrieV1
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           16
          </span>
          ms
         </li>
         <li>
          TrieV1
          <span class="number">
           1000000
          </span>
          次查询     cost time:
          <span class="number">
           780
          </span>
          ms
         </li>
         <li>
          TrieV1
          <span class="number">
           100000000
          </span>
          次查询   cost time:
          <span class="number">
           90949
          </span>
          ms
         </li>
         <li>
          TrieV2
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           50
          </span>
          ms
         </li>
         <li>
          TrieV2
          <span class="number">
           1000000
          </span>
          次查询     cost time:
          <span class="number">
           4361
          </span>
          ms
         </li>
         <li>
          TrieV2
          <span class="number">
           100000000
          </span>
          次查询   cost time:
          <span class="number">
           483398
          </span>
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
       </p>
       <p>
        总结一下，ArrayList和LinkedList方式实在太慢，跟最快的HashSet比将近慢约3个数量级，果断抛弃。Trie比HashSet慢约半个数量级，内存占用多约2.6倍，改进的TrieV1比Trie稍微节省一点内存约10%，速度差不多。进一步改进的TrieV2比Trie大大节省内存，只有HashSet的80%，不过速度比HashSet慢约1.5个数量级。
       </p>
       <p>
       </p>
       <p>
        TrieV2实现了节省内存的目标，节省了约70%，但是速度也慢了，慢了约10倍，可以对TrieV2做进一步优化，TrieNode的数组children采用有序数组，采用二分查找来加速。
       </p>
       <p>
       </p>
       <p>
        下面看看TrieV3的实现：
        <br/>
        <img src="http://dataunion.org/wp-content/uploads/2015/05/60d9ef5e-4e26-359f-be3d-bee8c2683d3e.png"/>
        <br/>
        使用了一个新的方法insert来加入数组元素，从无到有构建有序数组，把新的元素插入到已有的有序数组中，insert的代码如下：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          <span class="comment">
           /**
          </span>
         </li>
         <li>
          <span class="comment">
           * 将一个字符追加到有序数组
          </span>
         </li>
         <li>
          <span class="comment">
           * @param array 有序数组
          </span>
         </li>
         <li>
          <span class="comment">
           * @param element 字符
          </span>
         </li>
         <li>
          <span class="comment">
           * @return 新的有序数字
          </span>
         </li>
         <li>
          <span class="comment">
           */
          </span>
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          TrieNode[] insert(TrieNode[] array, TrieNode element){
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          length = array.length;
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (length ==
          <span class="number">
           0
          </span>
          ){
         </li>
         <li>
          array =
          <span class="keyword">
           new
          </span>
          TrieNode[
          <span class="number">
           1
          </span>
          ];
         </li>
         <li>
          array[
          <span class="number">
           0
          </span>
          ] = element;
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          array;
         </li>
         <li>
          }
         </li>
         <li>
          TrieNode[] newArray =
          <span class="keyword">
           new
          </span>
          TrieNode[length+
          <span class="number">
           1
          </span>
          ];
         </li>
         <li>
          <span class="keyword">
           boolean
          </span>
          insert=
          <span class="keyword">
           false
          </span>
          ;
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (
          <span class="keyword">
           int
          </span>
          i=
          <span class="number">
           0
          </span>
          ; i&lt;length; i++){
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (element.getCharacter() &lt;= array[i].getCharacter()){
         </li>
         <li>
          <span class="comment">
           //新元素找到合适的插入位置
          </span>
         </li>
         <li>
          newArray[i]=element;
         </li>
         <li>
          <span class="comment">
           //将array中剩下的元素依次加入newArray即可退出比较操作
          </span>
         </li>
         <li>
          System.arraycopy(array, i, newArray, i+
          <span class="number">
           1
          </span>
          , length-i);
         </li>
         <li>
          insert=
          <span class="keyword">
           true
          </span>
          ;
         </li>
         <li>
          <span class="keyword">
           break
          </span>
          ;
         </li>
         <li>
          }
          <span class="keyword">
           else
          </span>
          {
         </li>
         <li>
          newArray[i]=array[i];
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (!insert){
         </li>
         <li>
          <span class="comment">
           //将新元素追加到尾部
          </span>
         </li>
         <li>
          newArray[length]=element;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          newArray;
         </li>
         <li>
          }
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
       </p>
       <p>
        有了有序数组，在搜索的时候就可以利用有序数组的优势，重构搜索方法getChild：
        <br/>
        <img src="http://dataunion.org/wp-content/uploads/2015/05/d656efec-364d-3fbc-8bda-f56a03ba8352.png"/>
        <br/>
        数组中的元素是TrieNode，所以需要自定义TrieNode的比较方法：
        <br/>
        <img src="http://dataunion.org/wp-content/uploads/2015/05/b44d0fde-e36e-38d0-b9a5-bee94f5d4438.png"/>
        <br/>
        好了，一个基于有序数组的二分搜索的性能提升重构就完成了，良好的单元测试是重构的安全防护网，没有单元测试的重构就犹如高空走钢索却没有防护垫一样危险，同时，不过早优化，不做不成熟的优化是我们应该谨记的原则，要根据应用的具体场景在算法的时空中做权衡。
       </p>
       <p>
       </p>
       <p>
        OK，看看TrieV3的性能表现，当然了，内存使用没有变化，和TrieV2一样：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          TrieV2
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           50
          </span>
          ms
         </li>
         <li>
          TrieV2
          <span class="number">
           1000000
          </span>
          次查询     cost time:
          <span class="number">
           4361
          </span>
          ms
         </li>
         <li>
          TrieV2
          <span class="number">
           100000000
          </span>
          次查询   cost time:
          <span class="number">
           483398
          </span>
          ms
         </li>
         <li>
          TrieV3
          <span class="number">
           10000
          </span>
          次查询       cost time:
          <span class="number">
           21
          </span>
          ms
         </li>
         <li>
          TrieV3
          <span class="number">
           1000000
          </span>
          次查询     cost time:
          <span class="number">
           1264
          </span>
          ms
         </li>
         <li>
          TrieV3
          <span class="number">
           100000000
          </span>
          次查询   cost time:
          <span class="number">
           121740
          </span>
          ms
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
       </p>
       <p>
        提升效果很明显，约4倍。性能还有提升的空间吗？呵呵……
       </p>
       <p>
       </p>
       <p>
        <a href="https://github.com/ysc/word" target="_blank" title="https://github.com/ysc/word">
         代码托管于GITHUB
        </a>
       </p>
       <p>
       </p>
       <p>
        参考资料：
       </p>
       <p>
        1、
        <a href="http://pan.baidu.com/s/1qWwdhTE" target="_blank" title="http://pan.baidu.com/s/1qWwdhTE">
         中文分词十年回顾
        </a>
       </p>
       <p>
        2、
        <a href="http://pan.baidu.com/s/1i3n3Twp" target="_blank" title="http://pan.baidu.com/s/1i3n3Twp">
         中文信息处理中的分词问题
        </a>
       </p>
       <p>
        3、
        <a href="http://pan.baidu.com/s/1hqqTLfm" target="_blank" title="http://pan.baidu.com/s/1hqqTLfm">
         汉语自动分词词典机制的实验研究
        </a>
       </p>
       <p>
        4、
        <a href="http://pan.baidu.com/s/1gdeK6NT" target="_blank" title="http://pan.baidu.com/s/1gdeK6NT">
         由字构词_中文分词新方法
        </a>
       </p>
       <p>
        5、
        <a href="http://pan.baidu.com/s/1dD5TaVJ" target="_blank" title="http://pan.baidu.com/s/1dD5TaVJ">
         汉语自动分词研究评述
        </a>
       </p>
       <p>
       </p>
       <p>
        <a href="http://pan.baidu.com/share/link?shareid=1035458380&amp;uk=3157595467" target="_blank" title="http://pan.baidu.com/share/link?shareid=1035458380&amp;uk=3157595467">
         NUTCH/HADOOP视频教程
        </a>
       </p>
       <blockquote>
        <p>
         作者：yangshangchuan
        </p>
        <p>
         文章出处：
         <a href="http://yangshangchuan.iteye.com/blog/2031813">
          http://yangshangchuan.iteye.com/blog/2031813
         </a>
        </p>
       </blockquote>
      </div>
      <div>
       <strong>
        注：转载文章均来自于公开网络，仅供学习使用，不会用于任何商业用途，如果侵犯到原作者的权益，请您与我们联系删除或者授权事宜，联系邮箱：contact@dataunion.org。转载数盟网站文章请注明原文章作者，否则产生的任何版权纠纷与数盟无关。
       </strong>
      </div>
      <!--content_text-->
      <div class="fenxian">
       <!-- JiaThis Button BEGIN -->
       <div class="jiathis_style_32x32">
        <p class="jiathis_button_weixin">
        </p>
        <p class="jiathis_button_tsina">
        </p>
        <p class="jiathis_button_qzone">
        </p>
        <p class="jiathis_button_cqq">
        </p>
        <p class="jiathis_button_tumblr">
        </p>
        <a class="jiathis jiathis_txt jtico jtico_jiathis" href="http://www.jiathis.com/share" target="_blank">
        </a>
        <p class="jiathis_counter_style">
        </p>
       </div>
       <!-- JiaThis Button END -->
      </div>
     </article>
     <!--content-->
     <!--相关文章-->
     <div class="xianguan">
      <div class="xianguantitle">
       相关文章！
      </div>
      <ul class="pic">
       <li>
        <a href="http://dataunion.org/9008.html">
         <img src="http://dataunion.org/wp-content/uploads/2015/01/t01cfd13291abc18381_副本.png"/>
        </a>
        <a class="link" href="http://dataunion.org/9008.html" rel="bookmark" title="用MeCab打造一套实用的中文分词系统">
         用MeCab打造一套实用的中文分词系统
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/24220.html">
         <img src="http://dataunion.org/wp-content/uploads/2016/05/100910rrxp5plglxk4lcle-291x200.png"/>
        </a>
        <a class="link" href="http://dataunion.org/24220.html" rel="bookmark" title="520大数据：八成男性期待被表白 “套路”也是爱">
         520大数据：八成男性期待被表白 “套路”也是爱
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/23785.html">
         <img src="http://dataunion.org/wp-content/uploads/2016/04/u7145986293872240263fm21gp0-298x200.jpg"/>
        </a>
        <a class="link" href="http://dataunion.org/23785.html" rel="bookmark" title="Docker安全基准：22项新增要点概述">
         Docker安全基准：22项新增要点概述
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/23703.html">
         <img src="http://dataunion.org/wp-content/uploads/2016/04/1317020-300x163.jpg"/>
        </a>
        <a class="link" href="http://dataunion.org/23703.html" rel="bookmark" title="推荐：五个不容错过的数据科学家博客">
         推荐：五个不容错过的数据科学家博客
        </a>
       </li>
      </ul>
     </div>
     <!--相关文章-->
     <div class="comment" id="comments">
      <!-- You can start editing here. -->
      <!-- If comments are open, but there are no comments. -->
      <div class="title">
       期待你一针见血的评论，Come on！
      </div>
      <div id="respond">
       <p>
        不用想啦，马上
        <a href="http://dataunion.org/wp-login.php?redirect_to=http%3A%2F%2Fdataunion.org%2F16370.html">
         "登录"
        </a>
        发表自已的想法.
       </p>
      </div>
     </div>
     <!-- .nav-single -->
    </div>
    <!--Container End-->
    <aside id="sitebar">
     <div class="sitebar_list2">
      <div class="wptag">
       <span class="tagtitle">
        热门标签+
       </span>
       <div class="tagg">
        <ul class="menu" id="menu-%e5%8f%8b%e6%83%85%e9%93%be%e6%8e%a5">
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-1605" id="menu-item-1605">
          <a href="http://taidizh.com/">
           泰迪智慧
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-20884" id="menu-item-20884">
          <a href="http://www.transwarp.cn/">
           星环科技
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-3538" id="menu-item-3538">
          <a href="http://datall.org/">
           珈和遥感
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-20888" id="menu-item-20888">
          <a href="http://www.chinahadoop.cn/">
           小象学院
          </a>
         </li>
        </ul>
       </div>
      </div>
     </div>
     <div class="sitebar_list">
      <div class="textwidget">
       <div align="center">
        <a href="http://study.163.com/course/courseMain.htm?courseId=991022" target="_blank">
         <img src="http://dataunion.org/wp-content/uploads/2016/03/dv.jpg"/>
        </a>
       </div>
      </div>
     </div>
     <div class="sitebar_list">
      <h4 class="sitebar_title">
       文章分类
      </h4>
      <div class="tagcloud">
       <a class="tag-link-44" href="http://dataunion.org/category/industry/demo" style="font-size: 10.204724409449pt;" title="4个话题">
        Demo展示
       </a>
       <a class="tag-link-31" href="http://dataunion.org/category/experts" style="font-size: 15.826771653543pt;" title="52个话题">
        专家团队
       </a>
       <a class="tag-link-870" href="http://dataunion.org/category/tech/ai" style="font-size: 19.795275590551pt;" title="273个话题">
        人工智能
       </a>
       <a class="tag-link-488" href="http://dataunion.org/category/%e5%8a%a0%e5%85%a5%e6%95%b0%e7%9b%9f" style="font-size: 8pt;" title="1个话题">
        加入数盟
       </a>
       <a class="tag-link-869" href="http://dataunion.org/category/tech/viz" style="font-size: 17.204724409449pt;" title="93个话题">
        可视化
       </a>
       <a class="tag-link-30" href="http://dataunion.org/category/partners" style="font-size: 10.645669291339pt;" title="5个话题">
        合作伙伴
       </a>
       <a class="tag-link-889" href="http://dataunion.org/category/parterc" style="font-size: 11.582677165354pt;" title="8个话题">
        合作会议
       </a>
       <a class="tag-link-104" href="http://dataunion.org/category/books" style="font-size: 12.96062992126pt;" title="15个话题">
        图书
       </a>
       <a class="tag-link-220" href="http://dataunion.org/category/tech/base" style="font-size: 19.850393700787pt;" title="281个话题">
        基础架构
       </a>
       <a class="tag-link-219" href="http://dataunion.org/category/tech/analysis" style="font-size: 19.409448818898pt;" title="232个话题">
        数据分析
       </a>
       <a class="tag-link-887" href="http://dataunion.org/category/tech/dm" style="font-size: 13.291338582677pt;" title="17个话题">
        数据挖掘
       </a>
       <a class="tag-link-34" href="http://dataunion.org/category/tech" style="font-size: 20.732283464567pt;" title="404个话题">
        文章
       </a>
       <a class="tag-link-1" href="http://dataunion.org/category/uncategorized" style="font-size: 22pt;" title="693个话题">
        未分类
       </a>
       <a class="tag-link-4" href="http://dataunion.org/category/events" style="font-size: 14.503937007874pt;" title="29个话题">
        活动
       </a>
       <a class="tag-link-890" href="http://dataunion.org/category/tech/%e6%b7%b1%e5%ba%a6%e5%ad%a6%e4%b9%a0" style="font-size: 10.204724409449pt;" title="4个话题">
        深度学习
       </a>
       <a class="tag-link-221" href="http://dataunion.org/category/tech/devl" style="font-size: 18.968503937008pt;" title="193个话题">
        编程语言
       </a>
       <a class="tag-link-888" href="http://dataunion.org/category/career" style="font-size: 15.661417322835pt;" title="48个话题">
        职业规划
       </a>
       <a class="tag-link-5" href="http://dataunion.org/category/jobs" style="font-size: 14.11811023622pt;" title="25个话题">
        职位
       </a>
       <a class="tag-link-871" href="http://dataunion.org/category/industry" style="font-size: 15.716535433071pt;" title="49个话题">
        行业
       </a>
       <a class="tag-link-613" href="http://dataunion.org/category/industry/case" style="font-size: 16.984251968504pt;" title="84个话题">
        行业应用
       </a>
       <a class="tag-link-885" href="http://dataunion.org/category/industry/news" style="font-size: 17.425196850394pt;" title="102个话题">
        行业资讯
       </a>
       <a class="tag-link-10" href="http://dataunion.org/category/training" style="font-size: 14.228346456693pt;" title="26个话题">
        课程
       </a>
       <a class="tag-link-16" href="http://dataunion.org/category/sources" style="font-size: 15.661417322835pt;" title="48个话题">
        资源
       </a>
      </div>
     </div>
     <div class="sitebar_list">
      <h4 class="sitebar_title">
       功能
      </h4>
      <ul>
       <li>
        <a href="http://dataunion.org/wp-login.php?action=register">
         注册
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/wp-login.php">
         登录
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/feed">
         文章
         <abbr title="Really Simple Syndication">
          RSS
         </abbr>
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/comments/feed">
         评论
         <abbr title="Really Simple Syndication">
          RSS
         </abbr>
        </a>
       </li>
       <li>
        <a href="https://cn.wordpress.org/" title="基于WordPress，一个优美、先进的个人信息发布平台。">
         WordPress.org
        </a>
       </li>
      </ul>
     </div>
    </aside>
    <div class="clear">
    </div>
   </div>
   <!--main-->
   ﻿
   <footer id="dibu">
    <div class="about">
     <div class="right">
      <ul class="menu" id="menu-%e5%ba%95%e9%83%a8%e8%8f%9c%e5%8d%95">
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-18024" id="menu-item-18024">
        <a href="http://dataunion.org/category/partners">
         合作伙伴
        </a>
       </li>
       <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-20881" id="menu-item-20881">
        <a href="http://dataunion.org/contribute">
         文章投稿
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-20872" id="menu-item-20872">
        <a href="http://dataunion.org/category/%e5%8a%a0%e5%85%a5%e6%95%b0%e7%9b%9f">
         加入数盟
        </a>
       </li>
       <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-22441" id="menu-item-22441">
        <a href="http://dataunion.org/f-links">
         友情链接
        </a>
       </li>
       <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-20874" id="menu-item-20874">
        <a href="http://dataunion.org/aboutus">
         关于数盟
        </a>
       </li>
      </ul>
      <p class="banquan">
       数盟社区        ，
        做最棒的数据科学社区
      </p>
     </div>
     <div class="left">
      <ul class="bottomlist">
       <li>
        <a href="http://weibo.com/DataScientistUnion  " target="_blank" 　title="">
         <img src="http://dataunion.org/wp-content/themes/yzipi/images/weibo.png"/>
        </a>
       </li>
       <li>
        <a class="cd-popup-trigger" href="http://dataunion.org/16370.html#0">
         <img src="http://dataunion.org/wp-content/themes/yzipi/images/weixin.png"/>
        </a>
       </li>
      </ul>
      <div class="cd-popup">
       <div class="cd-popup-container">
        <h1>
         扫描二维码,加微信公众号
        </h1>
        <img src="http://dataunion.org/wp-content/themes/yzipi/images/2014-12-06-1515289049.png"/>
        <a class="cd-popup-close" href="http://dataunion.org/16370.html">
        </a>
       </div>
       <!-- cd-popup-container -->
      </div>
      <!-- cd-popup -->
     </div>
    </div>
    <!--about-->
    <div class="bottom">
     <a href="http://dataunion.org/">
      数盟社区
     </a>
     <a href="http://www.miitbeian.gov.cn/" rel="external nofollow" target="_blank">
      京ICP备14026740号
     </a>
     联系我们：
     <a href="mailto:contact@dataunion.org" target="_blank">
      contact@dataunion.org
     </a>
     <div class="tongji">
     </div>
     <!--bottom-->
     <div class="scroll" id="scroll" style="display:none;">
      ︿
     </div>
    </div>
   </footer>
   <!--dibu-->
  </div>
 </body>
</html>